package com.company.leetcode同类题型.String;

/**
 * 给一个字符串s,求s中的最长回文子串，有多个的话就返回其中一个
 */
public class longestPalindrome {
    public static void main(String args[]) {
        longestPalindrome longestPalindrome = new longestPalindrome();
        String res = longestPalindrome.longestPalindrome2("abccba");
        System.out.println(res + "，最大长度为：" + res.length());
    }

    /**
     * 动态规划方法
     * 令 p(i,j) 表示 字符串上 第i个到第j个字符之间的字符串 是否为 回文字符串
     * 令 s(i) 表示 第i个字符
     * 当 i =j时， p(i,j) = 1
     * 当 i = j+1时， p(i,j) = s(i)== s(j)
     * 当 i > j+1 时，p(i,j) = p(i+1,j-1) && s(i)== s(j)
     * <p>
     * 缺点：内存开销比较大，时间复杂度一般
     */
    public String longestPalindrome1(String s) {
        int len = s.length();
        int maxLong = 1;
        char ch[];
        boolean dp[][] = new boolean[len][len];
        ch = s.toCharArray();
        String maxStr = s.substring(0, 1);
        //长度是1的所有子串都是回文串

        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        //遍历所有的可能的长度
        for (int l = 2; l <= len; l++) {
            //遍历所有的起始位置
            for (int i = 0; i < len - l + 1; i++) {
                int j = i + l - 1;
                if (l == 2) {
                    if (ch[i] == ch[j]) {
                        dp[i][j] = true;
                        if (j - i + 1 > maxLong) {
                            maxStr = s.substring(i, j + 1);
                        }
                    }
                } else {
                    if (ch[i] == ch[j] && dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (j - i + 1 > maxLong) {
                            maxStr = s.substring(i, j + 1);
                        }
                    }
                }
            }
        }
        return maxStr;
    }


    /**
     * 中心扩散法
     */
    public String longestPalindrome2(String s) {
        if (s.equals("") || s.length() == 1) {
            return s;
        }

        char[] chars = s.toCharArray();
        int maxLen = 0;
        String maxLongStr = "";
        for (int i = 0; i < chars.length; i++) {
            int left = i;
            int right = i;
            //发现左边相同字符
            while (left - 1 >= 0 && chars[left - 1] == chars[i])
                left--;
            while (right + 1 < chars.length && chars[right + 1] == chars[i])
                right++;
            while (left - 1 >= 0 && right + 1 < chars.length && chars[left - 1] == chars[right + 1]) {
                left--;
                right++;
            }
            if (maxLen < right - left + 1) {
                maxLen = right - left + 1;
                maxLongStr = s.substring(left, right + 1);
            }
        }
        return maxLongStr;
    }

}
